package lc;

import java.util.HashMap;
import java.util.Map;

/**
 * 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
 *
 * 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
 *
 * 当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
 *
 */
public class Q837 {

    private Map<Integer, Double> bls;

    public double new21Game(int N, int K, int W) {
        // 组合数
        // 最后一个数是X时,之前得和是L，则有L < K,L+X >= K
        // 而满足后面得假设，则是L+X <= N
        // 定义了L，则X得条件很有限，其结果就是（X的数目）/W + (形成L的组合总数) / (所有相关组合总数)
        // 当K等于0时
        if (K == 0) {
            return 1.0;
        }
        double[] dp = new double[K + W];
        for (int i = K; i <= N && i < K + W; i++) {
            dp[i] = 1.0;
        }
        dp[K - 1] = 1.0 * Math.min(N - K + 1, W) / W;
        for (int i = K - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
        }
        return dp[0];

    }


    public static void main(String[] args) {
        final Q837 q837 = new Q837();
        // 前面抽的数可以是16,15,14,13,12,11
        // 对于16，后面的数是5,4,3,2,1,
        // 对于11，后面的数是10,9,8,7,6,5,4,3,2,1
        final double v = q837.new21Game(2,0,2);
        System.out.println(v);
//        System.out.println(q837.toBeL(4,10));
    }
}
